This invention relates generally to digital image scanners, and more specifically to a system for computing a resampling function on image data, in real time, before the data are stored into memory.
Image scanners convert a visible image on a document or photograph, or an image in a transparent medium, into an electronic form suitable for copying, storing or processing by a computer. Reflective image scanners typically have a controlled source of light, and light is reflected off the surface of a document, through an optics system, and onto an array of photosensitive devices. The photosensitive devices convert received light intensity into an electronic signal.
Sensor arrays may be one-dimensional or two-dimensional. For convenience of illustration, much of the present patent document is devoted to a hand-held scanner in which an optics system is used to focus a line on a document image onto a one-dimensional sensor array, but the invention is equally applicable to other types of imaging devices and to two-dimensional sensor arrays.
A picture element (pixel) may be defined as an area on the image being scanned, or as an area on a photosensor array, or as a set of numbers in the data representing an image. For document scanners and transparent film scanners, a pixel is commonly defined as an area on the surface of the document being scanned. For example, for document and transparent film scanners, a common specification is xe2x80x9cpixels per inchxe2x80x9d (or mm) as measured on the surface of the document being scanned.
Flatbed scanners typically include a linear sensor array that is moved relative to the original image, along an axis that is perpendicular to the axis of the sensor array. The position of the sensor array along the axis of movement is known. By sampling light intensity at appropriate intervals, pixels are determined on a uniform rectangular grid of pixel locations. Typically, each intensity measurement by each sensor element, in conjunction with the optics system, defines a single pixel on the original document and a single corresponding data value in a digital representation of the image.
A hand held scanner requires an operator to manually move a sensor array over an original image. In contrast to a flatbed scanner, manual manipulation is generally not perpendicular to the axis of the linear array, skew introduced by device rotation may change over time, and the movement is generally not at a uniform velocity. Therefore, in general, sensor element intensity measurements for a hand held scanner do not correspond to a uniform grid of pixel locations on the original document. In general, for a hand-held scanner, a uniform grid of pixels in a digital representation of an image must be computed from the non-uniform data from the original sensor data. The process of transforming a digital image from one set of pixel coordinates to another set of pixel coordinates is called geometric image resampling. Resampling from non-rectangular coordinates to rectangular coordinates is called image rectification.
A example of a scanning device for which the present invention is applicable may be found in U.S. Pat. No. 5,578,813 (Allen ""813), which is incorporated herein for all that it teaches and describes. Allen ""813 describes a hand-held scanner in which a scan-line is defined by the position of a linear array of photosensors. The linear sensor array measures image intensity at uniform positions between the ends of a scan-line. The scan-line may be skewed relative to the sides of the document being scanned and the skew may change as the scanner is moved. In general, the intensity samples measured by the scanner do not fall on a uniform rectangular grid. Separate position sensors monitor the positions of the ends of the scan-line, relative to a starting reference position, as the scanner is moved across the page. Position-tagged intensity data are stored in a memory. Later, the position-tagged intensity data are retrieved and used to compute image pixels at discrete points on a uniform rectangular pixel grid.
Ideally, the rectangular pixel grid has grid lines that are parallel to the sides of the document. For example, if a complete image is saved in memory, image analysis may be performed to determine margins, or edges of photographic images, or other information indicating the orientation of the document. Alternatively, the first scan-line may be used to define a reference position and one of two orthogonal directions. All scan-lines after the first may then be resampled to a rectangular grid that is defined relative to the first scan-line. In the following discussion, for convenience of illustration, pixel grids are depicted as square, having the same pitch for each of the two orthogonal directions. Likewise, for convenience of illustration, the optical sampling rate of the scanner along the direction of movement is depicted as the same as the optical sampling rate along the scan-line. In general, however, each of the two orthogonal directions of the pixel grid may have a different pixel pitch. Likewise, the scanner may have one optical sampling rate along the scan-line and a different optical sampling rate orthogonal to the scan line.
FIGS. 1 and 4 illustrate a prior art hand-held scanner to facilitate later discussion of the present invention in light of the prior art. Likewise, FIGS. 2, 3A and 3B illustrate prior art resampling. In FIG. 1, a hand-held scanner 100 is manually moved across the surface of a document 102 along a serpentine path 104. FIG. 2 illustrates a scan-line 200 with image intensities measured at discrete points 202 along the scan-line. Also illustrated in FIG. 2 is a grid of pixel locations 204. The lines of the pixel grid are ideally parallel to the sides of the document, but may be determined by the first scan-line as discussed above. Separate position sensors (see FIG. 4) are used to measure the relative movement of the ends of the scan-line 200. Given a starting reference position, and given the relative movements of the ends of the scan-line, and given the positions of the measured intensities 202 relative to the ends of the scan-line, the position of each measured intensity 202 may be determined relative to the reference position. The measured intensities 202, and sufficient information to determine the position of each measured intensity 202, are stored in a memory.
FIG. 3A illustrates a series of scan-lines (300, 302, 304, 306) determined by the position of the linear sensor array of the scanner as the scanner is moved across the document being scanned. Each intensity measurement from the scanner sensor array has been assigned a lower-case letter. FIG. 3A also illustrates a grid of pixel locations. The pixel locations have been assigned location notations relative to an arbitrary reference location (X0, Y0). To simplify illustration, in FIG. 3A, each scan-line has five photosensor elements and five intensity measurements. In a typical actual scanner, one linear sensor array may comprise thousands of individual photosensor elements.
FIG. 3B illustrates one method of computing intensities at the pixel locations from measured intensities from the scanner sensor array. One method for computing image rectification is bilinear interpolation using the intensities of the four closest neighboring sensor values. See, for example, Christopher D. Watkins, et al., Modern Image Processing: Warping, Morphing, and Classical Techniques, (Cambridge, Mass., Academic Press, 1993), pp. 99-102. A version of bilinear interpolation, as applied to FIG. 3A, is illustrated in FIG. 3B. In FIG. 3B, the (X,Y) locations of sensor values (d), (e), (i), and (j), and the (X,Y) location of pixel (X0+1, Y0) are all known. First, the intensity at point 308 (at X=X0+1) is determined by interpolation between the intensity values for sensor measurements (d) and (i), at the physical locations of sensor measurements (d) and (i). Next, the intensity at point 310 (at X=X0+1) is determined by interpolation between the intensity values for sensor measurements (e) and (j) at the physical locations of sensor measurements (e) and (j). Finally, the intensity at pixel (X0+1, Y0) is determined by interpolation, at Y0, along X=X0+1, between the intensities at points 308 and 310.
FIG. 4 illustrates a block diagram of a prior art system implementing a hand-held scanner in accordance with FIGS. 1, 2, 3A and 3B. A linear image sensor array 400 measures intensities along a scan-line determined by the position of array 400 on a document being scanned. Position sensors 402 sense the relative movements of the ends of the sensor array 400. Analog intensity measurements from the linear sensor array 400 are sequentially amplified (404) and sequentially converted to a numeric value by an analog-to-digital (A/D) converter 406. The outputs of the A/D 406 are sent to a random access memory (RAM) 410 via direct-memory-access (DMA). A processor 408 determines relative positions of the end-points of the scan-line and saves position data in the RAM 410. The processor, in conjunction with a specialized arithmetic unit for rectification (bilinear interpolation) 412, retrieves numeric sensor intensity measurements and position data from the RAM 410 and stores resampled pixel data back in the same RAM 410. The RAM 410 is large enough to buffer intensity measurements and to hold the resulting pixel data.
In FIG. 4, data are being written to RAM 410 by three devices (406, 408, and 412) and data are being read from RAM 410 by two devices (408, 412). As a result, arbitration electronics are required to limit reading to one device at a time, and writing to one device at a time. In addition, time is required to store numeric sensor intensity data from the A/D 406, and then to retrieve that same intensity data multiple times to compute pixel data. Processor firmware is required to manage rectification. As a result, the performance (speed) of the scanner is limited by processor firmware, by the RAM 410 and by the electronics (406, 408, 412) arbitrating for use of RAM. There is a need for a scanner with improved performance.
In a scanner in accordance with the invention, resampling of sensor data is computed in real time. Sensor data are not stored into an image memory, and processor firmware is not involved in rectification. As a result, the following advantages are realized:
1. The time required for firmware to store sensor intensity data and array position data into memory is eliminated.
2. The time required for firmware to compute addresses, to retrieve sensor intensity data and array position data from memory, and to send sensor intensity data and array position data to the rectifier, is eliminated.
3. Memory arbitration is simplified, and RAM access time is reduced, because fewer devices write to and read from the RAM.
4. RAM is reduced because there is no need to store sensor intensity data and array position data in RAM. Some separate buffering of sensor intensity and array position data is required, but only for less than two scan-lines of sensor data.
In an example embodiment for a single linear sensor array, sensor intensity data are entered into a data buffer configured as a fixed-length, first-in, first-out (FIFO) buffer. The data buffer is sufficiently long to hold one scan-line of intensity data plus two additional intensity values. An interpolator module receives data from the first two elements of the buffer and the last two elements of the buffer (along with position data). As new values are entered, old unneeded values are simply discarded. Some special conditions require a blank or null value to be inserted to maintain proper alignment. The system is extendable to color scanning by providing one data buffer and one interpolator module for each color.
In a second example embodiment, the data buffer is sufficiently long to hold one fall scan-line of intensity data, plus enough additional values to accommodate non-alignment of adjacent scan-lines. In the second example embodiment, when the ends of consecutive scan-lines are not aligned, the interpolator reads different buffer elements. This is in contrast to the first example embodiment, where the buffer elements being read by the interpolator are fixed, and blank or null values are inserted to accommodate alignment variations.